#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method,one test sample is not passed.
    // void traceback(vector<vector<string>> &tickets, vector<bool> &used)
    // {
    //     if (path.size() == tickets.size() + 1)
    //     {
    //         may_res = path;
    //         return;
    //     }
    //     for (size_t i = 0; i < tickets.size(); i++)
    //     {
    //         if (used[i] == true)
    //         {
    //             continue;
    //         }
    //         if (path.empty() && tickets[i][0] != "JFK")
    //         {
    //             continue;
    //         }
    //         if (!path.empty() && path.back() != tickets[i][0])
    //         {
    //             continue;
    //         }

    //         if (path.empty())
    //         {
    //             path.push_back(tickets[i][0]);
    //         }
    //         path.push_back(tickets[i][1]);

    //         used[i] = true;
    //         traceback(tickets, used);

    //         if (!may_res.empty())
    //         {
    //             return;
    //         }

    //         used[i] = false;
    //         path.pop_back();
    //         if (path.size() == 1)
    //         {
    //             path.pop_back();
    //         }
    //     }
    // }
    // vector<string> findItinerary(vector<vector<string>> &tickets)
    // {
    //     may_res.clear();
    //     path.clear();
    //     sort(tickets.begin(), tickets.end());
    //     vector<bool> used(tickets.size(), false);
    //     traceback(tickets, used);
    //     return may_res;
    // }
    // vector<string> may_res;
    // vector<string> path;

    // the solution of nook
    bool tracebacking(size_t nums, vector<string> &res)
    {
        if (res.size() == nums + 1)
        {
            return true;
        }
        auto it = target.find(res.back());
        if (it != target.end())
        {
            for (auto &map : it->second)
            {
                if (map.second > 0)
                {
                    res.push_back(map.first);
                    map.second--;
                    if (tracebacking(nums, res))
                    {
                        return true;
                    }
                    map.second++;
                    res.pop_back();
                }
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        target.clear();
        for (const auto &vec : tickets)
        {
            target[vec[0]][vec[1]]++;
        }
        vector<string> res;
        res.push_back("JFK");
        tracebacking(tickets.size(), res);
        return res;
    }
    unordered_map<string, map<string, int>> target;
};

int main()
{
    vector<vector<string>> tickets{{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
    Solution sol;
    vector<string> res = sol.findItinerary(tickets);
    for (auto str : res)
    {
        cout << str << " ";
    }
    cout << endl;
    return 0;
}